1. 투영과 거리
점 $x_0$ 에서 집합 $C$ 까지의 거리는 집합 내부의 점들까지 가능한 모든 거리 중 최소값으로 정의됩니다:
$\text{dist}(x_0, C) = \inf\{\|x_0 - x\| \mid x \in C\}$
이 거리를 달성하는 특정 최적화자는 투영 연산자입니다:
$P_C(x_0) = \text{argmin}\{\|x - x_0\| \mid x \in C\}$
간단한 초평면 $a^T x = b$ 는 $P_C(x_0) = x_0 + (b - a^T x_0)a/\|a\|_2^2$ 와 같은 아름다운 폐형 해를 갖습니다. 그러나 일반적인 집합에서는 이 문제는 여전히 제약 조건이 있는 최적화 문제로 남아 있습니다: 제약 조건 $f_i(x) \leq 0$ 및 $Ax = b$ 하에서 $\|x - x_0\|$ 를 최소화하기.
2. 함수 기하학
기하학적 제약을 목적 함수의 구성 요소로 다루기 위해 우리는 두 가지 강력한 함수적 '거울'을 사용합니다:
- 지표 함수 $I_C(x)$: $I_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}$. 이는 기하학적 구조를 수치적 처벌로 압축합니다.
- 지지 함수 $S_C(x)$: $S_C(x) = \sup_{y \in C} x^T y$. 이는 모든 방향에서의 경계 초평면을 통해 집합을 특성화합니다.
공집합이 아니며 닫힌 집합 $C \in \mathbf{R}^n$ 는 체비셰프 집합 (모든 $x_0$ 에 대해 유일한 투영을 갖는) 경우에만 볼록.
만약 $C$ 가 볼록하고 노름이 엄격하게 볼록하다고 가정합시다. 만약 서로 다른 두 점 $u, v \in C$ 가 $\|u - x_0\| = \|v - x_0\| = d$ 를 만족한다면, 그 중점 $w = (u+v)/2$ 는 $C$ 에 속합니다 (볼록성에 의해).
노름의 엄격한 볼록성에 따라: $\|w - x_0\| = \|\frac{1}{2}(u - x_0) + \frac{1}{2}(v - x_0)\| < \frac{1}{2}\|u - x_0\| + \frac{1}{2}\|v - x_0\| = d$.
이는 $d$ 가 최소 거리였다는 가정과 모순됩니다. 따라서 투영은 반드시 유일해야 합니다.
주의사항 8.4: 노름 의존성
우리는 종종 다음과 같은 방법으로 분리 초평면을 구성합니다: $(P_C(x_0) - x_0)^T (x - (1/2)(x_0 + P_C(x_0))) = 0$. 주의하세요! 이 특정 구성은 유클리드 노름에 대해서만 유효합니다. 일반적인 노름은 직각의 개념을 더 세밀하게 다뤄야 합니다.